import java.util.ArrayList;
import java.util.List;

// 二叉树的锯齿形层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
public class Code02_ZigzagLevelOrderTraversal {
    // 不提交这个类
    public static class TreeNode {
        // 节点的值
        public int val;
        // 节点的左子节点
        public TreeNode left;
        // 节点的右子节点
        public TreeNode right;
    }

    // 提交以下的方法
    // 用每次处理一层的优化bfs就非常容易实现
    // 如果测试数据量变大了就修改这个值
    public static int MAXN = 2001;
    public static TreeNode[] queue = new TreeNode[MAXN];
    public static int l, r;

    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 用于存储最终的锯齿形层序遍历结果
        // 外层List表示二叉树的层，内层List表示每层的节点值
        List<List<Integer>> ans = new ArrayList<>();
        if (root!= null) {
            // 初始化队列的头指针和尾指针
            l = r = 0;
            // 将根节点加入队列
            queue[r++] = root;
            // false代表从左往右
            // true代表从右往左
            boolean reverse = false;
            // 只要队列里还有节点，就继续循环
            while (l < r) {
                // 确定当前层的节点数量
                int size = r - l;
                // 用于存储当前层节点的值
                ArrayList<Integer> list = new ArrayList<>();
                // 根据reverse的值确定节点的收集顺序
                // reverse == false，从左到右收集节点
                // reverse == true，从右到左收集节点
                for (int i = reverse? r - 1 : l, j = reverse? -1 : 1, k = 0; k < size; i += j, k++) {
                    // 获取队列中的节点
                    TreeNode cur = queue[i];
                    // 将节点的值添加到当前层的列表中
                    list.add(cur.val);
                }
                // 将当前层的节点的左子节点和右子节点（如果存在）加入队列
                for (int i = 0; i < size; i++) {
                    // 取出队列头部的节点
                    TreeNode cur = queue[l++];
                    if (cur.left!= null) {
                        // 将左子节点加入队列
                        queue[r++] = cur.left;
                    }
                    if (cur.right!= null) {
                        // 将右子节点加入队列
                        queue[r++] = cur.right;
                    }
                }
                // 将当前层的节点值列表添加到结果中
                ans.add(list);
                // 切换遍历方向
                reverse =!reverse;
            }
        }
        // 返回最终的锯齿形层序遍历结果
        return ans;
    }
}